1. Field of the Invention
This invention relates to computerized information management and, more particularly, to systems and methods of optimization that can be used independently or as part of a hybrid global/local approach.
2. Description of the Related Art
A class of problems known as "Optimization Problems" arises often in diverse areas such as resource allocation, event planning, and the like. These problems are characterized in having a set of elements and a set of possible resources, and in calling for a particular assignment of elements to resources that approaches optimality in some measurable manner. Processes using artificial intelligence (AI) techniques have been applied to such optimization problems to find solutions.
"Elements," as used herein, refers to a set of things, such as tasks, variables, or people, that is assigned to one or more resources. For example, elements may be tasks or people in a scheduling problem or variables in a register allocation problem. "Resources," in contrast, refers to a set of things to which the elements are assigned. For example, resources may be manufacturing lines capable of performing tasks, doctors capable of meeting with patients, or registers capable of holding variables. In general, the set of resources is relatively fixed and defines the domain of the problem while the set of elements typically changes for each problem instance. In the example of patients and doctors described above, the set of patients (elements) may change every day, but the set of doctors (resources) remains relatively stable.
Other optimization problems include planning feasible schedules for meetings, assisting scientists in interpreting images from artificial vision devices, and even allowing cartographers to select colors for countries or other municipal areas when designing maps. A particular example of an optimization problem is scheduling a manufacturing process for fiber optic cables. This type of problem features multiple tasks/jobs and multiple manufacturing lines on which jobs can be run. Each job corresponds to a cable to be made, and each cable has certain characteristics that affect how and when it can be manufactured. These include a release time, a deadline, and a length for each job.
Continuing with this example, each line may have different characteristics affecting which cables can be made on each, and how fast each line is. Furthermore, there is a changeover cost between any two adjacent jobs on a given line. A goal for such a sample problem might be to minimize lateness (missed deadlines) and changeover costs.
This type of optimization problem may be decomposed into subproblems involving subschedules for the individual lines. It is desirable in such a problem to find a assignment of line schedules that have each job scheduled exactly once and to do so with minimal cost.
Optimization problems are related to another set of problems known as constraint-satisfaction problems, or CSPs. One approach to dealing with such problems uses artificial intelligence (AI) search techniques in one of two ways. The first way is known as "systematic" because under this approach, every possible set of element-resource pairings is eventually considered, unless a set of pairings that meets all of the constraints is found at some point in the process. These processes often rely on maintaining a database of possible reasons why certain assignments, or groups of assignments, will not satisfy the constraints of the problem. The sets of reasons indicating assignments that do not work are commonly referred to as sets of "nogoods". When a process of this class fails to provide a set of workable assignments, one can be sure that no workable set of assignments exists. Numerous such systematic processes are known, for instance as described in M. L. Ginsberg, Dynamic Backtracking, JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 1:25-46, 1993.
The second way is known as "nonsystematic" and is typically faster to find a solution. However, because processes of this class do not keep track of whether they have considered all possible sets of element-resource pairings, where such processes do not yield a solution, one cannot know whether a workable set of assignments exists but has not been found, or whether no workable set of assignments exists. A well-known example of such a nonsystematic technique is the GSAT technique, now known under an improved version as WSAT and described in B. Selman, et al., Local Search Strategies for Satisfiability Testing, PROCEEDINGS 1993 DIMACS WORKSHOP ON MAXIMUM CLIQUE, GRAPH COLORING, AND SATISFIABILITY, 1993.
Several other known strategies within these two broad classes of processes have been employed to solve CSPs.
One known process is to simply apply a heuristic, or "rule of thumb," and to see whether the heuristic results in an acceptable solution. One such heuristic might be: If machine A is available, use it; otherwise if machine B is available use it; otherwise if machine C is available use it; otherwise wait for machine A to finish and then use it. In some instances, such a technique works very well and provides a simple solution. When the heuristic fails, however, alternate techniques must be used.
One possible alternate scheme, known as iterative sampling, or isamp, involves following random paths, or probes, from a starting point to a candidate solution until eventually a path leading to an acceptable solution is discovered. At each node on a path, one of the successor nodes is selected at random and followed; next, one of the successors to that node is selected, and so on, until either a "goal node", i.e., acceptable solution, or a dead end is reached. If a path terminates at a dead end, a new probe is begun from the original starting point.
This process samples with replacement, resulting in a uniform chance of finding a goal node on any particular probe. Accordingly, the probability of achieving a goal node progresses uniformly to 1 as the number of probes grows without limit.
Iterative sampling works well in applications exhibiting high solution densities, but not otherwise.
Another scheme, known as "backtracking," uses the heuristic approach as far as possible. When the heuristic is found to fail, the last decision before the failure is changed, unless all possible changes at that point have already been tried. If they have, the decision prior to that is changed, and so on. This process works well where heuristics early in the process are more reliable than those later in the process, because it does not revisit the earliest decisions until all of the subsequent paths have been found to fail. Unfortunately, in most real-world problems, heuristics generally become more reliable as a solution is approached and the problem is reduced in size.
Similarly, a number of approaches have been developed for processing optimization problems. As with CSP, heuristic approaches have been widely used, and have the advantage of speed and scalability (i.e., ability to handle problem instances of increasing size gracefully). Exact approaches, on the other hand, often provide results that are closer to the theoretically optimal results, but require much more time-consuming processing to do so.
The Operations Research (OR) community has a history of successfully solving large optimization problems that can be formulated as Linear Programming/Integer Programming (LP/IP) problems. For truly large problems, it is not computationally possible to pass a full definition of a problem (all possible rows and all possible columns) to an LP/IP engine. To even enumerate, let alone solve, such large problems would take more resources than feasible for many commercial purposes.
The particular type of problem described above is somewhat decomposable into subproblems, but is not fully decomposable because there is interaction among the subproblems. This class of problem allows for parts of different solutions to be recombined to form new solutions. Typical OR approaches to such problems begin with generating one or more initial solutions using heuristic methods. These initial solutions may range from poor to good in quality, but are usually far from optimal. These initial heuristic solutions are used to "seed" an LP/IP engine, and the process of generating this initial set of solutions is known as "seeding."
The engine then solves the problem based on the initial, or "seed," solutions. It recombines parts of the various initial solutions to provide the best LP solution (and sometimes IP) that can be produced from those solutions. It also identifies in what parts of the problem the engine is having the hardest time finding a solution. This information about what parts are hard is then used as guidance in the next step of the process.
The next step in the conventional OR process is to divide the problem into its subproblems and then generate new solutions for each subproblem using the feedback from the previous call to the LP/IP engine. To reduce the complexity of the problem, the subproblems are solved in isolation from each other. The subproblem solutions attempt to address precisely those problems that were identified by the previous pass. These partial solutions are then fed back into the LP and the process repeats with the LP/IP engine identifying new problem areas on each iteration. This process of generating new subproblem solutions based on feedback from the LP/IP engine is called "new column generation." The process of generating new partial solutions is the heart of the traditional OR approach, but is also the weakest spot in that approach. Traditional methods spend most of their time doing new column generation (generating new partial solutions), and the quality of the partial solutions tends to be far from optimal.
The generation of new partial solutions has a large search component and that is where artificial intelligence (AI) methods become involved. It was hoped that AI techniques would be better at new column generation and thus would move the LP/IP engine towards better solutions faster than do existing OR techniques.
Numerous methods are known for processing optimization problems, as disclosed in the following references, which are hereby incorporated by reference for background information:
M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, W. H. Freeman, 1979; PA1 H. Kautz and B. Selman, Pushing the envelope: Planning, propositional logic, and stochastic search, in Proceedings of the National Conference on Artificial Intelligence, AAAI Press, Portland, Oreg., 1996; PA1 James M. Crawford, An Approach to Resource Constrained Project Scheduling, in Artificial Intelligence and Manufacturing Research Planning Workshop, 1996; PA1 Bart Selman, Henry A. Kautz and Bram Cohen, Local search strategies for satisfiability testing, in Cliques, Coloring, and Satisfiability: The Second DIMACS Implementation Challenge, Rutgers University, October, 1993; PA1 B. Selman, H. Levesque and D. Mitchell, A new method for solving hard satisfiability problems, in Proceedings of the National Conference on Artificial Intelligence, pp. 440-446, 1992; PA1 Gilbert P. Syswerda, Generation of Schedules using a Genetic Procedure, U.S. Pat. No. 5,319,781; PA1 Barry R. Fox and Mark Ringer, Planning and Scheduling Benchmarks, available at http://www.NeoSoft.com/.about.benchmrx/, 1995; PA1 Richard M. Stallman and Gerald J. Sussman, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, AI, 9:135-36, 1977; PA1 E. Aarts and J. Korts, Simulated Annealing and Boltzman Machines, Wiley, 1989; PA1 G. L. Nemhauser, M. W. P. Savelsbergh and G. C. Sigismondi, MINTO, A Mixed INTeger Optimizer, Operations Research Letters, 1994, 15:47-58; PA1 G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1988; PA1 G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research, 8:101-111,1960; PA1 C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh and P. Vance, Branch-and-Price: Column Generation for Solving Huge Integer Programs, Operations Research, 1996; PA1 CPLEX Optimization, Inc.; Using the CPLEX Callable Library and CPLEX Mixed Integer Library, Version 4.0, 1996; PA1 F. Glover and M. Laguna, Tabu Search, Kluwer, 1997; PA1 Thomas A. Feo and Mauricio G. C. Resende, Greedy Randomized Adaptive Search Procedures, Journal of Global Optimization, 6:109-133, 1995.
Despite the plethora of research and development in this area, there is still a need for improved solutions that provide faster and more accurate results to optimization problems. Known processes for handling optimization problems are all lacking in one way or another, and no known teaching provides an adequately robust process that does not suffer from any of these failings.